COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00013 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a26.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Theorem:\hfill}

Any (partial) function that can be computed on one of these machines can be
computed on all of them:

\smallskip\disleft 25pt:(1):
2 or more stacks

\smallskip\disleft 25pt:(2):
1 or more 2-way tapes

\smallskip\disleft 25pt:(3):
1 or more 1-way tapes

\smallskip\disleft 25pt:(4):
2 or more counters.

\smallskip\noindent
Let $L$ and $R$ be stacks, viewed as strings with the head of $L$ on the
right and the head of~$R$ on the left. (This makes it possible to view
$LR$ as a single string with a movable boundary between the two parts.)
Both are initially empty. Let $T=\langle \ldots t↓{-2},t↓{-1},t↓0,t↓1,t↓2\ldots
\rangle$ be a two-way tape, and $U=\langle u↓1,u↓2,\ldots\rangle$
a~one-way tape, both initially all blank. Let $C$ and $D$ be two counters,
initially zero.

\smallskip\disleft 25pt:(1):
To simulate $T$ using $L$ and $R$, we keep in $L$ the string
$\# t↓{-a}\ldots t↓{-2}t↓{-1}$,
and in $R$ the string $t↓0t↓1t↓2\ldots t↓b\#$, where these include
all the non-blank characters of $T$ (by induction, there are only finitely
many). Initialize $L$ and~$R$ by pushing \#\ on each. Each operation
given below is preceded by:

\smallskip\halign{\qquad\qquad\lft{\tt #}\cr
IF TOP(L)=\#\ THEN PUSH BLANK ON L;\cr
IF TOP(R)=\#\ THEN PUSH BLANK ON R;\cr}

$$\vcenter{\halign{\lft{#}\qquad&\lft{#}\cr
Operation on $T$&Simulating operation\cr
\noalign{\smallskip}
{\tt IF $t↓0={\tt X}$ THEN $\alpha$ ELSE $\beta$}&{\tt IF TOP(R)=X THEN}\cr
&\q $\alpha$ {\tt ELSE} $\beta$\cr
Move tape left&{\tt IF TOP(R)$=a↓1$ THEN PUSH $a↓1$ ON L}\cr
&{\tt ELSE IF TOP(R)$=a↓2$ THEN PUSH $a↓2$ ON L}\cr
&\q $\vdots$\cr
&{\tt ELSE IF TOP(R)$=a↓m$ THEN PUSH $a↓m$ ON L;}\cr
&\q {\tt POP R.}\cr
Move tape right&Similar, interchanging {\tt L} and {\tt R}.\cr
Write $a↓i$ on tape&{\tt POP R;}\cr
&{\tt PUSH} $a↓i$ {\tt ON R.}\cr}}$$

\smallskip\disleft 25pt:(2):
To simulate $U$ using $T$, we initially put a marker $\vdash$ on~$T$
which represents the non-existent left half of~$U$; the initialization
is

\smallskip\halign{\qquad\qquad\lft{\tt #}\cr
WRITE $\vdash$ ON T\cr
MOVE TAPE LEFT.\cr}

\smallskip\noindent
Thereafter, all operatons on $T$ are the same as on~$U$, except for:

$$\vcenter{\halign{\lft{#}\qquad&\lft{#}\cr
Operation on $U$&Operation on $T$\cr
\noalign{\smallskip}
{\tt MOVE TAPE RIGHT}&{\tt MOVE TAPE RIGHT;}\cr
&{\tt IF $t↓0=\;\vdash$ THEN}\cr
&\qq {\tt MOVE TAPE LEFT}\cr}}$$

\smallskip\disleft 25pt:(3):
To simulate $C$ and $D$ using $U$, we initialize $U$ to $\vdash$ in~$U↓1$.
$C$~and $D$ are represented by having 1's in positions $U↓2U↓4U↓6\ldots U↓{2C}$
and positions $U↓3U↓5U↓7\ldots U↓{2D+1}$, $\vdash$~in position~$U↓1$, and
blanks elsewhere. All operations on $U$ are preceded by

\smallskip\halign{\qquad\qquad\lft{\tt #}\cr
WHILE tape character $≠\;\vdash$ DO\cr
\qq MOVE U RIGHT\cr}

\def\tmo{\hbox{$\vcenter{\hbox{\tt .}\vskip-8pt\hbox{\tt -}}$}} %. over -
%use $\!$ on both sides of \tmo

$$\vcenter{\halign{\lft{#}\qquad&\lft{#}\cr
Operation on $C$, $D$&Operation on $U$\cr
\noalign{\smallskip}
{\tt IF C=0 THEN $\alpha$ ELSE $\beta$}&{\tt MOVE TAPE LEFT;}\cr
&\q {\tt (* TO $U↓2$ *)}\cr
&{\tt IF} tape character $=$ blank\cr
&\q {\tt THEN $\alpha$ ELSE $\beta$}\cr
{\tt IF D=0 THEN $\alpha$ ELSE $\beta$}&{\tt MOVE TAPE LEFT;}\cr
&{\tt MOVE TAPE LEFT;}\cr
&\q {\tt (* TO $U↓3$ *)}\cr
&{\tt IF}  tape character $=$ blank\cr
&\q {\tt THEN $\alpha$ ELSE $\beta$}\cr
{\tt C:=C+1}&{\tt MOVE TAPE RIGHT;}\cr
&{\tt WHILE} tape character $=1$ {\tt DO}\cr
&\q {\tt BEGIN}\cr
&\q {\tt MOVE TAPE RIGHT}\cr
&\q {\tt MOVE TAPE RIGHT}\cr
&\q {\tt END;}\cr
&{\tt WRITE 1 ON TAPE}\cr
{\tt C:=C$\!$\tmo$\!$1}&Exercise for the reader\cr
{\tt D:=D+1}&Exercise for the reader\cr
{\tt D:=D$\!$\tmo$\!$1}&Exercise for the reader\cr}}$$

\vfill\eject

\smallskip\disleft 25pt:(4A):
To simulate several (say,~4) counters $U$, $V$, $W$, $X$ using two counters
$C$ and~$D$, at the beginning of each simulated operation we have
$2↑U3↑V5↑W7↑X$ in~$C$, and 0 in~$D$. Initially $C=1$ and $D=0$.

$$\vcenter{\halign{\lft{#}\quad&\lft{#}\cr
Typical operation on $U$, $V$, $W$, $X$&Operation on $C$, $D$\cr
\noalign{\smallskip}
Test if $V=0$&Transfer contents of $C$ to $D$ and back,\cr
&keeping track of number {\tt MOD 3}.\cr 
&If $≠0$ at the end, $V=0$.\cr
{\tt V:=V+1}&{\tt WHILE C$≠$0 DO}\cr
&\q {\tt BEGIN C:=C-1; D:=D+1 END}\cr
&{\tt WHILE D$≠$0 DO}\cr
&\q {\tt BEGIN D:=D-1; C:=C+3 END}\cr
{\tt V:=V-1}&{\tt WHILE C$≠$0 DO}\cr
&\q {\tt BEGIN C:=C-1; D:=D+1; END}\cr
&{\tt WHILE D$≠$0 DO}\cr
&\q {\tt BEGIN D:=D-3; C:=C+1 END}\cr}}$$

\smallskip\disleft 25pt:(4B):
To simulate a stack $S$ containing $x↓0x↓1x↓2\ldots x↓n$, where each $x↓i$
is, for convenience, a~1 or a~2, using counters $C$, $D$, we keep the
number $\Sigma x↓i2↑i$ in counter~$C$. Initially, the counter is~0,
corresponding to an empty stack. Our convention is that $S$ is the head
of the stack. All operations on $C$, $D$ are prefaced by setting $D=0$.

$$\vcenter{\halign{\lft{#}\quad&\lft{#}\cr
Operation on $S$&Operation on $C$, $D$\cr
\noalign{\smallskip}
Test if $S$ empty&Test if $C=0$\cr
Test if $x↓0=1$&Test if $C$ is odd\cr
Push $x$ on $C$&$C:=2C+x$\cr
Pop $C$&$C:=(C-1)\hbox{ DIV }2$\cr}}$$

\smallskip\disleft 25pt::
All the above $C$, $D$ operations are readily programmed.

\smallskip\disleft 25pt:(4):
To simulate $k$ stacks using two counters, first simulate $k+1$ counters,
then use one of them to simulate each stack, using the last, as above,
as a temporary.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 23, 1984

\bye